package bszt.aliwenyu;

import java.util.*;

public class Code03 {

    /**
     * 题目描述
     * LYA定义了一个神奇数字num，其要满足num=a^2+b^3+c^4，其中a,b,c都为质数。于是LYA想知道在1-n中有多少个这样的神奇数字呢，请你告诉LYA
     * <p></p>
     * 输入格式
     * 第一行为t，表示有t组数据
     * 接下来有t行，每行为一个整数n
     * <p></p>
     * 输出格式
     * 输出为t行，每行为一组答案
     */

    public static void main(String[] args) {
        int N = 1000001;
        boolean[] st = new boolean[N];
        List<Integer> prime = new ArrayList<>();

        for (int i = 2; i < N; i++) {
            if (!st[i]) prime.add(i);
            for (int j = i; j < N; j += i) st[j] = true;
        }

        Set<Long> s = new HashSet<>();

        for (int a : prime) {
            if ((long) a * a >= N) break;
            for (int b : prime) {
                if ((long) a * a + (long) b * b * b >= N) break;
                for (int c : prime) {
                    long val = (long) a * a + (long) b * b * b + (long) c * c * c * c;
                    if (val >= N) break;
                    s.add(val);
                }
            }
        }

        List<Long> v = new ArrayList<>(s);
        Collections.sort(v);

        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int m = v.size();
        while (t-- > 0) {
            int x = sc.nextInt();
            int l = 0, r = m;
            while (l < r) {
                int mid = l + r >> 1;
                if (v.get(mid) > x) r = mid;
                else
                    l = mid + 1;
            }
            System.out.println(l);
        }
    }
}

